package william.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/5
 * @description <a href="https://leetcode.cn/problems/isomorphic-strings/description/">...</a>
 */
public class Leetcode205_同构字符串 {
    /**
     * 借助Map实现
     * 维护两个字符串的双向映射表
     * 同时遍历两个字符串,判断映射是否匹配
     * <p>
     * 时间复杂度O(N) 两个字符串各遍历一次
     * 空间复杂度O(N) 需要额外申请两个字符串长度的Map
     */
    public boolean isIsomorphic(String s, String t) {
        //边界条件校验
        if (s.length() != t.length()) {
            return false;
        }

        int N = s.length();

        //维护两个字符串的双向映射
        Map<Character, Character> s2t = new HashMap<>(N);
        Map<Character, Character> t2s = new HashMap<>(N);

        //同时遍历两个字符串,判断映射是否匹配
        for (int i = 0; i < N; i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if (!s2t.containsKey(sc) && !t2s.containsKey(tc)) { //构造新映射
                s2t.put(sc, tc);
                t2s.put(tc, sc);
                continue;
            }

            //判断映射是否匹配
            if (s2t.containsKey(sc) && s2t.get(sc) != tc) {
                return false;
            }
            if (t2s.containsKey(tc) && t2s.get(tc) != sc) {
                return false;
            }
        }

        //映射匹配,返回true
        return true;
    }
}
